package com.gyg.程序员面试金典;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */

/**
 * 面试题 04.02. 最小高度树
 * 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
 * 解题思路：
 * （1）利用递归二分的思想，将问题划分成若干个子问题，
 * （2）在有序排列的数组中，中间节点就是根节点，
 * （3）左边的数组就是该节点的左子树，右边数组就是该节点右子树
 * （4）利用这一思想，将问题划分成多个相同的子问题。
 * （5）直到左子树或右子树为空时，跳出递归。
 */
public class T04_02 {
    public TreeNode sortedArrayToBST(int[] nums) {
//        调用递归函数
        return new T04_02().helper(nums, 0, nums.length);
    }

    /**
     * 利用递归来分解问题
     *
     * @param nums  原来的数组
     * @param left  该树从数组左边的哪个下标开始
     * @param right 该树中节点的长度，也可以说是到数组右边哪个下标+1处结束
     * @return
     */
    public TreeNode helper(int[] nums, int left, int right) {
        //        （1）设置递归出口；如果左边标识和右边标识相等，这个时候是不会指向划定的数组范围内的数的
        if (left == right) {
        //        （2）跳出循环递归
            return null;
        }
        //       （3） 取出数组的中间值，作为根节点
        int middle = (left + right) / 2;
        TreeNode treeNode = new TreeNode(nums[middle]);
        //       （4） 该元素左边的数组组成该树的左子树
        treeNode.left = helper(nums, left, middle);
        //        （5）该元素的右边数组组成该树的右子树
        treeNode.right = helper(nums, middle + 1, right);
        //          （6）返回该子树
        return treeNode;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
